package leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * Created by Ghost on 2015/2/3.
 */
public class Unique_Binary_Search_Trees_II {
    public List<TreeNode> generateTrees(int n) {
        return generateTrees(1,n+1);
    }

    private List<TreeNode> generateTrees(int leftBoard, int rightBoard){
        List<TreeNode> rst = new LinkedList<TreeNode>();
        if(leftBoard==rightBoard){
            TreeNode treeNode = null;
            rst.add(treeNode);
        }
        else{
            for(int i=leftBoard;i<rightBoard;i++){
                List<TreeNode> left = generateTrees(leftBoard,i);
                List<TreeNode> right = generateTrees(i+1,rightBoard);

                for(TreeNode l:left){
                    for(TreeNode r:right){
                        TreeNode root = new TreeNode(i);
                        root.left = l;
                        root.right = r;

                        rst.add(root);
                    }
                }
            }
        }
        return rst;
    }

    public static void main(String[] args){
        Unique_Binary_Search_Trees_II unique_binary_search_trees_ii = new Unique_Binary_Search_Trees_II();
        List<TreeNode> rst =unique_binary_search_trees_ii.generateTrees(1);
        System.out.println();
    }
}
